# 快速排序实现
# 稳定性：不稳定
# 最优时间复杂度：O(nlogn)
# 最坏时间复杂度：O(n^2)
def quick_sort(arr, start, end):
    # 递归终止条件
    if start >= end:
        return

    left = start  # 左游标
    right = end  # 右游标

    # 把0位置，当作中间值(可以优化，每一轮为了保证左右子序列数量大体一致，不至于退化到O(n^2)，可以把取中间值的逻辑优化一下)
    mid = arr[left]

    print(arr, left, right, mid)

    while left < right:
        while left < right and arr[right] >= mid:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] < mid:
            left += 1
        arr[right] = arr[left]

    # 此时left = right
    arr[left] = mid

    quick_sort(arr, start, left - 1)
    quick_sort(arr, left + 1, end)


if __name__ == "__main__":
    arr = [7, 4, 9, 1, 5, 6, 3, 10, 2]
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)
